class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr)
        return;

        ListNode* newhead2=new ListNode(0);
        //计算链表的长度
        ListNode* slow=head,*fast=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* tmp=slow->next;
        slow->next=nullptr;
        //头插法逆序
        while(tmp)
        {
            ListNode* next=tmp->next;
            tmp->next=newhead2->next;
            newhead2->next=tmp;
            tmp=next;
        }
        ListNode* ret=new ListNode(0);
        ListNode* tail=ret;
        ListNode *cur1=head,*cur2=newhead2->next;

        while(cur1)
        {
            tail->next=cur1;
            tail=tail->next;
            cur1=cur1->next;

            if(cur2)
            {
                tail->next=cur2;
                tail=tail->next;
                cur2=cur2->next;
            }
        }
        delete newhead2;
        delete ret;
    }
};